package com.example.shujujiegousuanfa.链表;

/**
 * 该类将会参考JDK中LinkedList的实现，实现自己的!-单-!链表类-不使用哨兵节点。
 * 实现的功能主要是面试中比较常见的题目和链表的基本操作，没有实际生产用途，仅供学习参考。
 * <p>
 * 具有的功能如下所示：
 * <p>
 * <p>
 * 1.  判断链表是否为空
 * 2.  返回链表的长度
 * 3.  正向遍历链表
 * 4.  反向遍历链表
 * 5.  链表头部添加节点
 * 6.  链表尾部添加节点
 * 7.  指定值后面添加节点
 * 8.  所有指定值后面添加节点
 * 9.  指定值前面添加节点
 * 10. 所有指定值前面添加节点
 * 11. 返回链表的头
 * 12. 返回链表的尾
 * 13. 判断链表是否有环，如果有返回环的长度和入口点
 * 14. 删除指定值一个节点
 * 15. 删除指定值所有节点
 * 16. 在一个排序的链表中，删除重复的节点
 * 17. 在一个无序的链表中，删除重复的节点
 * 18. 查找节点是否存在
 * 19. 查找指定值节点个数
 * 20. 反转链表
 * 21. 返回链表中间节点-快慢指针
 * 22. 合并两个有序的单链表
 * 23. 合并K个有序的单链表
 * 24. 链表的选择排序
 * 25. 链表的冒泡排序
 * 26. 链表的归并排序
 * 27. 链表的快速排序
 * 28. 返回自身与另外一个链表的公共节点
 * 29. 返回倒数第k个节点
 * 30. 实现一个LRU缓存
 * 31. 判断链表是否是回文
 */
public class MyLinkedList<E extends Comparable> {
    /**
     * 哨兵节点，即链表的第一个元素
     */
    Node<E> first;

    public MyLinkedList() {
    }

    public static <E> boolean isEmpty(Node<E> head) {
        return head == null;
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addLast(1);
        myLinkedList.addLast(2);
        myLinkedList.addLast(3);
        System.out.println(myLinkedList);
    }

    public static <E> int size(Node<E> head) {
        Node<E> temp = head;
        int size = 0;
        while (temp != null) {
            size++;
            temp = temp.next;
        }
        return size;
    }

    /**
     * 合并两个有序的单链表
     * 插入合并一个有序的单链表
     * 注意，不允许自己合并自己
     *
     * @param
     */
    public static <T extends Comparable> MyLinkedList<T> mergeSortedList(MyLinkedList<T> thisList, MyLinkedList<T> otherList) {
        if (thisList == otherList) {
            throw new IllegalArgumentException("不允许自己与自己合并");
        }
        MyLinkedList<T> newMyLinkedList = new MyLinkedList<>();
        Node<T> thisNode = thisList.first;
        Node<T> otherNode = otherList.first;
        newMyLinkedList.first = mergeTwoNode(thisNode, otherNode);
        return newMyLinkedList;
    }

    public static <T extends Comparable> Node<T> mergeTwoNode(Node<T> thisNode, Node<T> otherNode) {
        if (thisNode == otherNode) {
            throw new IllegalArgumentException("不允许自己合并自己");
        }
        Node<T> resultNode = new Node<>(null, null);
        Node<T> resultTemp = resultNode;
        while (thisNode != null && otherNode != null) {
            if (thisNode.item.compareTo(otherNode.item) > 0) {
                resultTemp.next = otherNode;
                otherNode = otherNode.next;
                resultTemp = resultTemp.next;
            } else {
                resultTemp.next = thisNode;
                thisNode = thisNode.next;
                resultTemp = resultTemp.next;
            }
        }
        if (thisNode != null) {
            resultTemp.next = thisNode;
        }
        if (otherNode != null) {
            resultTemp.next = otherNode;
        }
        return resultNode.next;
    }

    /**
     * 合并K个有序的单链表
     * 仿照归并排序的思路所写
     *
     * @param
     */
    public static <T extends Comparable> MyLinkedList<T> mergeKSortedList(MyLinkedList<T>... myLinkedLists) {
        return mergeKSortedList(myLinkedLists, 0, myLinkedLists.length - 1);
    }

    private static <T extends Comparable> MyLinkedList<T> mergeKSortedList(MyLinkedList<T>[] myLinkedLists, int lo, int hi) {
        // 递归终止条件
        if (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            MyLinkedList<T> leftList = mergeKSortedList(myLinkedLists, lo, mid);
            MyLinkedList<T> rightList = mergeKSortedList(myLinkedLists, mid + 1, hi);
            return mergeSortedList(leftList, rightList);
        }
        return myLinkedLists[lo];
    }

    /**
     * 1. 判断链表是否为空
     */
    public boolean isEmpty() {
        return isEmpty(first);
    }

    /**
     * 2. 返回链表的长度
     */
    public int size() {
        return size(first);
    }

    /**
     * 3. 正向遍历链表
     */
    public void printList() {
        Node<E> temp = first;
        while (temp != null) {
            System.out.println(temp.item);
            temp = temp.next;
        }
    }

    /**
     * 4. 反向遍历链表
     * 因为要反向遍历链表，考虑使用递归，因为递归调用栈既是一个天然的先入后出的队列
     */
    public void printListReverse() {
        Node<E> temp = first;
        printListReverse(temp);
    }

    private void printListReverse(Node<E> e) {
        if (e != null) {
            printListReverse(e.next);
            System.out.println(e.item);
        }
    }

    /**
     * 5. 链表头部添加节点
     *
     * @param e
     */
    public void addFirst(E e) {
        Node<E> temp = first;
        final Node<E> newNode = new Node<E>(e, null);
        // 如果头结点为空，新加结点就是头结点
        // 如果头结点不为空，则新加结点的next就是头结点，并且将头结点设置为新加结点
        if (temp == null) {
            first = newNode;
        } else {
            newNode.next = temp;
            first = newNode;
        }
    }

    /**
     * 6. 链表尾部添加节点
     * 直接找到最后一个节点，添加到最后一个节点的next
     * 特殊情况：如果链表长度为0，直接令first为新插入节点
     * 引入哨兵节点处理特殊情况，简化边界条件
     *
     * @param e <E> 要插入的值
     */
    public void addLast(E e) {
        Node<E> temp = first;
        Node<E> newNode = new Node<E>(e, null);
        if (temp == null) {
            first = newNode;
        } else {
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = newNode;
        }
    }



    /**
     * 7. 指定值得后面添加节点
     * 如果链表中已经有了重复的值，以排在最前面的为准.
     * 如果插入成功，则返回true
     * 如果插入失败，则返回false
     * 特殊情况：
     * 1. 如果链表是空的，直接返回false
     *
     * @param aimValue <E>
     */
    public boolean addBefore(E aimValue, E insertValue) {
        Node<E> temp = first;
        if (temp == null) {
            return false;
        } else {
            while (temp != null) {
                if (temp.item.equals(insertValue)) {
                    Node<E> newNode = new Node<E>(aimValue, null);
                    newNode.next = temp.next;
                    temp.next = newNode;
                    return true;
                } else {
                    temp = temp.next;
                }
            }
            return false;
        }
    }

    /**
     * 8. 所有指定值后面添加节点
     * 链表中所有指定值的后面都添加节点
     * 返回插入值的个数
     * 逻辑：
     * 1. 如果头结点为空，直接返回0
     *
     * @param aimValue <E>
     */
    public int addBeforeAll(E aimValue, E insertValue) {
        // 插入值的个数
        int count = 0;
        if (first == null) {
            return 0;
        } else {
            Node<E> temp = first;
            while (temp != null) {
                if (temp.item.equals(aimValue)) {
                    Node<E> newNode = new Node<>(insertValue, null);
                    newNode.next = temp.next;
                    temp.next = newNode;
                    count++;
                    // 由于是在temp后面加了一个指定值，所以，要令temp = temp.next.next;
                    temp = temp.next.next;
                } else {
                    temp = temp.next;
                }
            }
        }
        return count;
    }

    /**
     * 9. 指定值前面添加节点
     *
     * @param aimValue    目标值
     * @param insertValue 要插入的值
     * @return 返回插入是否成功
     */
    public boolean addAfter(E aimValue, E insertValue) {
        // 如果头结点为空，直接返回false
        if (first == null) {
            return false;
        } else {
            // 特殊情况：
            // 如果链表只有一个头结点，且是目标值，直接插入到头结点前面，
            // 并重新设置头结点即可
            if (first.item.equals(aimValue)) {
                Node<E> newNode = new Node<>(insertValue, null);
                newNode.next = first;
                first = newNode;
                return true;
            } else {
                // 此处进入到else，表示链表不止仅有一个头结点
                Node<E> temp = first;
                // 可以发现这里判断不到头结点是否等于目标值，所以将之列为特殊情况
                while (temp.next != null) {
                    if (temp.next.item.equals(aimValue)) {
                        Node<E> newNode = new Node<>(insertValue, null);
                        newNode.next = temp.next;
                        temp.next = newNode;
                        return true;
                    } else {
                        temp = temp.next;
                    }
                }
                return false;
            }
        }
    }

    /**
     * * 10. 所有指定值前面添加节点
     * 返回添加的次数
     *
     * @param aimValue    目标值
     * @param insertValue 要插入的值
     * @return 返回插入的个数
     */
    public int addAfterAll(E aimValue, E insertValue) {
        // 如果头结点为空，表示一定没有插入的位置，直接返回0。
        int count = 0;
        if (first == null) {
            return count;
        } else {
            // 特殊情况：
            // 如果链表只有一个头结点，且是目标值，直接插入到头结点前面，
            // 并重新设置头结点即可
            Node<E> temp = first;
            if (first.item.equals(aimValue)) {
                Node<E> newNode = new Node<>(insertValue, null);
                newNode.next = first;
                first = newNode;
                count++;
                temp = temp.next;
            }
            // 可以发现这里判断不到头结点是否等于目标值，所以将之列为特殊情况
            while (temp.next != null) {
                if (temp.next.item.equals(aimValue)) {
                    Node<E> newNode = new Node<>(insertValue, null);
                    newNode.next = temp.next;
                    temp.next = newNode;
                    temp = temp.next.next;
                    count++;
                } else {
                    temp = temp.next;
                }
            }
            return count;
        }
    }

    /**
     * 11. 返回链表的头结点
     *
     * @return
     */
    public Node<E> head() {
        return first;
    }

    /**
     * 12. 返回链表的尾
     *
     * @return
     */
    public Node<E> tail() {
        if (first == null) {
            return first;
        } else {
            Node<E> temp = first;
            while (temp.next != null) {
                temp = temp.next;
            }
            return temp;
        }
    }

    /**
     * 13. 判断链表是否有环，如果有，返回环的长度和入口点
     *
     * @return
     */
    public CircleResult getCircleResult() {
        return new CircleResult.Builder().build();
    }

    /**
     * 14. 删除指定值一个节点
     * 特殊情况：
     * 如果链表长度为0,或者aimValue为null，直接返回false，
     * 如果删除的是头结点，直接移动头结点即可
     * 如果删除的不是头结点
     *
     * @param
     */
    public boolean removeOneNode(E aimValue) {
        if (first == null || aimValue == null) {
            return false;
        }
        if (first.item.equals(aimValue)) {
            first = first.next;
            return true;
        } else {
            Node<E> temp = first;
            while (temp.next != null) {
                if (temp.next.item.equals(aimValue)) {
                    temp.next = temp.next.next;
                    return true;
                }
                temp = temp.next;
            }
        }
        return false;
    }

    /**
     * 15. 删除指定值所有节点,返回删除的个数
     *
     * @param
     */
    public int removeAllNode(E aimValue) {
        if (first == null || aimValue == null) {
            return 0;
        }
        // 循环删除头结点，直到头结点不为目标值
        int count = 0;
        while (first != null && first.item.equals(aimValue)) {
            first = first.next;
            count++;
        }
        if (first != null) {
            Node<E> temp = first;
            while (temp.next != null) {
                if (temp.next.item.equals(aimValue)) {
                    temp.next = temp.next.next;
                    count++;
                } else {
                    temp = temp.next;
                }
            }
        }
        return count;
    }

    /**
     * 16. 在一个排序的链表中，删除重复的节点
     * <p>
     * 思路一：暴力破解
     * 思路二：双指针法
     * <p>
     * 双指针法利用了排序的性质，由于链表已经排序，如果有重复的节点，那么重复的节点一定是排列在一起的。
     * 假设定义指针x为nodeX，指针y为nodeY。
     * 如果nodeX == nodeY，则另nodeY = nodeY.next;
     * 如果nodeX != nodeY, 则另nodeX.next = NodeY,删除nodeX->nodeY之间的节点，并另nodex = nodeX.next
     * nodeY = nodeY.next
     * Ruguo
     */
    public void removeOrderListDupNode() {
        // 首先确保头结点和aimValue不是null
        if (first == null) {
            throw new IllegalArgumentException("目标值不可为null");
        }
        Node<E> nodeX = first;
        Node<E> nodeY = first.next;
        while (nodeY != null) {
            if (nodeX.item.equals(nodeY.item)) {
                nodeY = nodeY.next;
                // 如果nodeY == null，则表示循环要结束了
                // 如果不另nodeX.next = null,可以会导致没有正确删除节点
                // 例如：如果链表是 1,2,2,2,2
                // 当nodeX = 2，nodeY = null时，循环直接跳出了，并没有删除节点。
                if (nodeY == null) {
                    nodeX.next = null;
                }
            } else {
                nodeX.next = nodeY;
                nodeX = nodeX.next;
                nodeY = nodeY.next;
            }
        }
    }

    /**
     * 17. 在一个无序的链表中，删除重复的节点
     * 思路一：对链表进行排序，调用removeOrderListDupNode
     * 思路二：暴力法，直接双重遍历，发现重复的删除后者
     *
     * @param aimValue
     */
    public void removeNotOrderListDupNode(E aimValue) {
    }

    /**
     * 18. 查找指定值节点是否存在
     * 思路：直接遍历一遍
     *
     * @param aimValue
     * @return
     */
    public boolean isExist(E aimValue) {
        Node<E> temp = first;
        while (temp != null) {
            if (temp.item.equals(aimValue)) {
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    /**
     * 19. 查找指定值节点的个数
     * 思路：直接遍历一遍
     *
     * @param aimValue
     * @return
     */
    public int countNode(E aimValue) {
        int count = 0;
        if (aimValue == null) {
            return 0;
        }
        Node<E> temp = first;
        while (temp != null) {
            if (temp.item.equals(aimValue)) {
                count++;
            }
            temp = temp.next;
        }
        return count;
    }

    /**
     * 翻转链表:非递归做法
     * 思路：
     * 非递归的做法可以简单的理解为创建一个新的头结点，依次遍历原链表，将原链表的数据依次插入到新链表的头结点前面。
     * 比如有一个链表为 1->2->3->2->5
     * 现在创建一个新的头结点，值为原链表的头结点的值
     * 1->NULL
     * 依次将2 3 2 5插入到新头结点的前面
     * 次序为
     * 2->1->null
     * 3->2->1->null
     * 2->3->2->1->null
     * 5->2->3->2->1->null
     * 我们可以对上述代码进行优化，
     * 其实我们并不需要创建的一个新的头结点，
     * 我们一次遍历链表，将后续的链表插入到自己的头结点前面即可，注意要
     * 更新链表的头结点。
     */
    public void reverse() {
        Node<E> temp = first;
        while (temp != null && temp.next != null) {
            Node<E> t = temp.next;
            temp.next = t.next;
            t.next = first;
            first = t;
        }
    }

    /**
     * 反转从位置m到n的链表。
     *
     * @param start
     * @param end
     */
    public void reverse(int start, int end) {
        // 1 <=m<=n<=链表长度

    }

    /**
     * 翻转链表：递归做法
     * 这种反转链表的递归做法很好理解，就是用递归替换了while循环。
     * 通过这种做法我们可以做一个总结。
     * while循环体 -> 递归
     * 循环体外的逻辑 -> 上层函数
     * 循环体的循环条件 -> 递归的终止条件
     * 循环体内的逻辑 -> 递归函数终止条件下面写 + 某尾递归调用自己。
     * 此处插入一个Python的写法，利用了Python的多元赋值
     * def reverse(head):
     * p,rev = head,None
     * while p:
     * rev,rev.next,p = p,rev,p.next
     * return rev
     */
    public void reverseRecur() {
        Node<E> temp = first;
        reverseRecur(temp);
    }

    private void reverseRecur(Node<E> temp) {
        if (temp == null || temp.next == null) {
            return;
        }
        Node<E> t = temp.next;
        temp.next = t.next;
        t.next = first;
        first = t;
        reverseRecur(temp);
    }

    /**
     * 非尾递归做法
     * 思路
     * https://blog.csdn.net/fx677588/article/details/72357389
     */
    public void reverseRecur2() {
        first = reverseRecur2(first);
    }

    private Node<E> reverseRecur2(Node<E> first) {
        if (first == null || first.next == null) {
            return first;
        }
        Node<E> newFirst = reverseRecur2(first.next);
        first.next.next = first;
        first.next = null;
        return newFirst;
    }

    /**
     * 返回链表中间节点-快慢指针
     * 使用快慢指针
     * 一开始起步相同，快指针每一次移动两个节点
     * 慢指针每次移动一个节点，当快指针到达末尾的时候，慢指针指向的位置就是中间节点。
     *
     * @return
     */
    public Node<E> middleNode() {
        return middleNode(first);
    }

    private Node<E> middleNode(Node<E> head) {
        if (head == null) {
            return null;
        }
        Node<E> slowNode = head;
        Node<E> fastNode = head.next;
        while (fastNode != null && fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }
        return slowNode;
    }

    /**
     * 链表的插入排序。 TODO ganju感觉有bug，谨慎参考，待修改
     * 思路：创建一个新的链表，遍历源链表，以此插入到新链表里面
     */
    public void insertSort() {
        if (first == null || first.next == null) {
            // 如果链表长度为0或者1，则不需要排序
            return;
        }
        Node<E> head = first;

        Node<E> newFirst = new Node<>(null, null);
        Node<E> tempFirst = newFirst;
        while (head != null) {
            // head!=null 表示要将源链表遍历完
            // 找到插入点
            while (tempFirst != null && tempFirst.next != null && head.item.compareTo(tempFirst.next.item) > 0) {
                tempFirst = tempFirst.next;
            }
            Node<E> temp = head;
            head = head.next;
            temp.next = tempFirst.next;
            tempFirst.next = temp;
            tempFirst = newFirst;

        }
    }

    /**
     * 链表的选择排序
     * 算法思想：选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换
     * 方式，最终得到一个有序序列。
     *
     * @param
     */
    public void selectSort() {

        Node<E> sortedTail = first;

        while (sortedTail != null) {
            Node<E> minNode = findMinNode(sortedTail);
            swapTwoNodeValue(sortedTail, minNode);
            sortedTail = sortedTail.next;
        }
    }

    // 返回head节点后面值最小的节点
    private Node<E> findMinNode(Node<E> head) {
        Node<E> minNode = head;
        head = head.next;
        while (head != null) {
            if (head.item.compareTo(minNode.item) < 0) {
                minNode = head;
            }
            head = head.next;
        }
        return minNode;
    }

    private void swapTwoNodeValue(Node<E> nodeOne, Node<E> nodeTwo) {
        // 交换两个节点中的值
        E temp = nodeOne.item;
        nodeOne.item = nodeTwo.item;
        nodeTwo.item = temp;
    }

    /**
     * 链表的冒泡排序
     */
    public void bubbleSort() {
        if (first == null || first.next == null) {
            return;
        }
        // 冒泡排序一轮走完，会让最大的沉底
        // 所有已经有序的起始点，都在最后。
        // 已经有序节点的起始点
        Node<E> sortedStart = null;

        while (first != sortedStart) {
            Node<E> p = first;
            for (; p.next != null && p.next != sortedStart; p = p.next) {
                if (p.item.compareTo(p.next.item) > 0) {
                    swapTwoNodeValue(p, p.next);
                }
            }
            sortedStart = p;
        }
    }

    /**
     * 链表的归并排序
     * 思路：
     * 利用快慢指针，找到链表的中间节点，之后递归合并
     */
    public void mergeSort() {
        first = mergeSort(first);
    }

    private Node<E> mergeSort(Node<E> head) {
        // 递归终止条件：链表长度为1
        if (head == null || head.next == null) {
            return head;
        }
        // 可以看到，归并排序的关键是找到中间节点，并拆封成两个链表，直到链表长度为1了，在递归的合并。
        Node<E> middleNode = middleNode(head);
        Node<E> leftNode = head;
        Node<E> rightNode = middleNode.next;
        middleNode.next = null;
        leftNode = mergeSort(leftNode);
        rightNode = mergeSort(rightNode);
        Node<E> newNode = mergeTwoNode(leftNode, rightNode);
        return newNode;
    }

    /**
     * 链表的快速排序
     * 只交换值
     */
    public void quickSortValue() {
        // 如果链表长度为0或者1，直接返回，不需要排序。
        if (first == null || first.next == null) {
            return;
        }
        quickSortValue(first, null);
    }

    private void quickSortValue(Node<E> head, Node<E> tail) {
        if (head != tail && head.next != null) {
            Node<E> mid = partition(head, tail);
            quickSortValue(head, mid);
            quickSortValue(mid.next, tail);
        }

    }

    private Node<E> partition(Node<E> lowNode, Node<E> hiNode) {
        // 利用选择排序找到基准点
        E key = lowNode.item;
        Node<E> loc = lowNode;

        for (Node<E> i = lowNode.next; i != hiNode; i = i.next) {
            // 如果遇到了一个比基准点小的，都放在基准点左边
            if (i.item.compareTo(key) < 0) {
                loc = loc.next;
                swapTwoNodeValue(loc, i);
            }
        }
        // 最后让基准点与loc交换数值，并返回loc
        swapTwoNodeValue(loc, lowNode);
        return loc;
    }


    /**
     * 链表的快速排序
     * 交换节点
     */
    public void quickSortNode() {
        first = quickSortNode(first);
    }

    private Node<E> quickSortNode(Node<E> head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node<E> preHead = new Node<>(null, null);
        preHead.next = head;
        quickSortNode(preHead, head, null);
        return preHead.next;
    }

    private void quickSortNode(Node<E> preHead, Node<E> head, Node<E> tail) {
        if (head != tail && head.next != tail) {
            Node<E> middleNode = partition(preHead, head, tail);
            quickSortNode(preHead, preHead.next, middleNode);
            quickSortNode(middleNode, middleNode.next, tail);
        }
    }

    private Node<E> partition(Node<E> preHead, Node<E> head, Node<E> tail) {
        E key = head.item;
        Node<E> littleNode = new Node<>(null, null);
        Node<E> largeNode = new Node<>(null, null);
        Node<E> t_littleNode = littleNode;
        Node<E> t_largeNode = largeNode;

        for (Node<E> i = head.next; i != tail; i = i.next) {
            if (i.item.compareTo(key) < 0) {
                t_littleNode.next = i;
                t_littleNode = i;
            } else {
                t_largeNode.next = i;
                t_largeNode = i;
            }
        }
        // preHead -> littleNode.next -> ...->t_littleNode->head->largeNode.next->...->t_largeNode->tail
        t_largeNode.next = tail;
        head.next = largeNode.next;
        t_littleNode.next = head;
        preHead.next = littleNode.next;
        return head;
    }

    /**
     * 返回自身与另外一个链表的公共节点
     *
     * @param otherLinkedList
     * @return
     */
    public Node<E> commonNode(MyLinkedList<E> otherLinkedList) {
        return null;
    }

    /**
     * 返回倒数第k个节点
     *
     * @return
     */
    public Node<E> reciprocalKNode() {
        return null;
    }

    public static class Node<E> {
        // 结点类
        E item;
        Node<E> next;

        Node(E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }
}

